package sword.offer;

/**
 * 给定一个m x n 二维字符网格board 和一个字符串单词word 。如果word 存在于网格中，返回 true ；否则，返回 false 。
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
 * 同一个单元格内的字母不允许被重复使用。
 *
 * 链接：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class Twelve {
    /**
     * 使用DFS 深度优先搜索
     * 我能想到最直接的方法就是，以二位数组中每个元素作为字符串的第一个元素，然后做深度遍历。
     * 所以我们需要一个双重for循环，和深度遍历
     * */
    class Solution {
        public boolean exist(char[][] board, String word) {
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[0].length; j++) {
                    if(recur(board, i, j, word, 0)){
                        return true;
                    }
                }
            }
            return false;
        }

        /**
         * 基线条件：
         * 当搜索的字符串已经完成了，返回true  即 k == word.length()-1
         * 当搜索的当前元素越界，或者和word的第k个字符不相同 返回false
         * 相同则继续搜索知道搜索的字符串已经完成为止
         * */
        public boolean recur(char[][] board, int x, int y, String word,int k){
            // 越界的情况 或者 不相同的情况 返回false
            if(x < 0 || y < 0 || x >= board.length || y >= board[0].length || board[x][y] != word.charAt(k)){
                return false;
            }
            if(k == word.length()-1){
                return true;
            }
            // 设置该节点已经访问 已经访问的标志 要设置成和搜索的字符永远不会相等的字符  比如空格
            board[x][y] = ' ';
            boolean res =recur(board,x-1,y, word, k + 1) || recur(board,x+1,y, word, k + 1)
                    || recur(board,x,y-1, word, k + 1) || recur(board , x, y+1, word, k+1);
            board[x][y] = word.charAt(k);
            return res;
        }
    }
}
